1. Field of the Invention
The present invention relates to a router using distributed processing, and more particularly to a router using distributed processing of FIB (Forwarding Information Base) look-up and/or real-time traffic control algorithms in the packet switching network such as the Internet.
2. Description of the Prior Art
As generally known in the art, the main motivation is to provide telecommunication services to the internet users. For this, the FIB look-up is performed by the processor or processing elements on the line interface modules to make the processing faster. A fair queuing algorithm is used to avoid congestion in the routers. Fair queuing is a packet scheduling algorithm based on the calculation of virtual finish time of each packet and sorting the packets in the increasing order of the virtual finish time. The packets are transmitted in that order. By doing this, the packets are transmitted within the virtual finish time. For the calculation of the virtual finish time, the information of the packet arrival time (Ai), the reserved rate (R), the packet length (Li), and the virtual finish time of the previous packet of the connection (Fi−1) is required. The virtual finish time of the first packet of each connection is obtained by adding the first packet arrival time to the packet length divided by the reserved rate; F1=A1+L1/R. Afterwards, the virtual finish time is obtained by adding the larger between the packet arrival time and the virtual finish time of the previous packet to the packet length divided by the reserved rate; Fi=max(Ai, Fi−1)+Li/R.
Real-time traffic QoS guarantee in the packet switching network is achieved on a small scale at the experimental level, but large scale implementation for commercial services by the internet service provider is still in difficulties. Increasing speed of links and increasing number of ports cause problems in that demands on computing resources such as processor and memory for implementing fair queuing scheduler get larger. There are opinions that implementation of fair queuing schedulers is not practical for very large router.
There are two approaches to solve these problems. Firstly, it has been pursued to lower the computing complexity of the scheduler. Simplification of the scheduling algorithm decreases the demand on processing power. Secondly, it is increasing the processing speed of the hardware. Dedicated hardware can be devised to speed up the algorithm. These two methods have limitation and we are in doubt about the economy of the solutions.